本发明公开了一种用于差分队列服务系统的数据包快速入队方法。差分队列服务系统的队列由差分队列服务队列和其他队列构成,差分队列服务队列包括先进先出区间和差分队列服务区间。先进先出区间位于队列前部,差分队列服务区间紧随其后。当差分队列服务队列长度小于先进先出区间长度时,新到的数据包依据先进先出服务入队规则插入先进先出区间;否则,该数据包依据差分队列服务入队规则插入差分队列服务区间。这种方法加快了新到数据包的入队速度,使差分队列服务系统能满足高速网络中服务质量的要求。
1.一种用于差分队列服务系统的数据包快速入队方法,差分队列服务系统的队列由差分队列服务队列和其他队列构成,差分队列服务队列包括先进先出区间和差分队列服务区间;所述先进先出区间位于队列前部,差分队列服务区间紧随其后;设先进先出区间长度为L,差分队列服务区间阈值为H,其特征在于所述方法具体包括如下步骤:1)新数据包到达系统,从该数据包的包头读取端到端时延;2)判断端到端时延是否大于0:是,则跳往步骤3);否,则放入其他队列,本数据包入队过程结束;3)判断当前差分队列服务队列的长度是否小于L:是,则执行步骤4);否,则跳往步骤5);4)判断当前差分队列服务队列的服务时间与该数据包的服务时间之和是否不大于该数据包所容忍的最大时延:是,则放入先进先出区间的尾部,本数据包入队过程结束;否,则放入其他队列,本数据包入队过程结束;5)xa0确定新数据包在差分队列服务区间的插入位置;6)判断新数据包在差分队列服务区间的插入位置是否同时满足如下条件,a)该数据包插入位置前面所有数据包的服务时间与该数据包的服务时间之和不大于该数据包所容忍的最大时延,b)该数据包插入位置后面的数据包的时延保障不受影响:是,则将数据包插入步骤5)所确定的位置,本数据包入队过程结束;否,则将该数据包放入其他队列,本数据包入队过程结束。
2.根据权利要求1所述的一种用于差分队列服务系统的数据包快速入队方法,其特征在于,所述差分队列服务队列为一个,其他队列为一个或一个以上。
3.根据权利要求1或2所述的一种用于差分队列服务系统的数据包快速入队方法,其特征在于,所述差分队列服务队列调度优先级高于其他队列。
4.根据权利要求1所述的一种用于差分队列服务系统的数据包快速入队方法,其特征在于所述步骤5)确定新数据包在差分队列服务区间的插入位置包括:判断当前差分队列服务队列的长度是否小于L与H之和:是,则用顺序查找法确定;否,则用二分查找法确定。
5.根据权利要求4所述的一种用于差分队列服务系统的数据包快速入队方法,其特征在于插入位置满足:新数据包与当前差分队列服务区间的数据包按数据包的最迟离开时刻升序排列。
6.根据权利要求4所述的一种用于差分队列服务系统的数据包快速入队方法,其特征在于所述顺序查找法从当前差分队列服务区间尾部开始查找。
7.根据权利要求4所述的一种用于差分队列服务系统的数据包快速入队方法,其特征在于所述二分查找法从当前差分队列服务区间的实际长度的中间位置开始查找。
8.根据权利要求4所述的一种用于差分队列服务系统的数据包快速入队方法,其特征在于所述方法查找的范围均为当前差分队列服务区间的实际长度。
9.根据权利要求1所述的一种用于差分队列服务系统的数据包快速入队方法,其特征在于所述先进先出区间长度L由如下条件确定:服务完先进先出区间的数据包所需时间,不得大于时间t1与时间t2之和;所述时间t1为先进先出区间查找特定位置时间,该位置使新数据包与该区间的数据包按数据包的可容忍的最迟离开队列时刻升序排列;所述时间t2为将新数据包插入查找到的位置的时间。
10.根据权利要求1所述的一种用于差分队列服务系统的数据包快速入队方法,其特征在于所述差分队列服务区间阈值H由如下条件确定:用顺序查找法的平均查找时间不得大于用二分查找法的平均查找时间。技术领域
xa0xa0xa0xa0本发明属于队列管理和分组调度技术领域,具体涉及一种用于差分队列服务系统的数据包快速入队方法。
背景技术
xa0xa0xa0xa0在现有的互联网技术中,有两种经典的服务质量方案,即综合服务(Integratedxa0Services)和区分服务(Differentiatedxa0Services)。它们提供服务质量的做法是,将缓存分成多个优先级队列,时延敏感的业务流进入高优先级的队列,其他业务流进入低优先级的队列。分组调度器采用优先级队列调度、加权公平队列调度或其他调度算法在多个队列中选择数据包进行调度。但是,一般路由器中可能有几十条至几百条甚至更多的服务质量保障队列,在极短的时间内要求调度器在这些队列中选择一个数据包进行转发的做法对处理器和存储器访问操作提出了严格的要求。实际上,由于硬件实现上的难度,在一个数据包转发期间在所有队列中选择下一数据包的行为限制了队列的数量,从而也限制了综合服务和区分服务对服务质量保障的粒度与公平性。xa0xa0xa0xa0针对综合服务和区分服务中存在的问题,一种差分队列服务(Differentiatedxa0Queueingxa0Services)方案被提出(参考文献[1]xa0Jiangxa0S.,“Granularxa0differentiatedxa0queueingxa0servicesxa0forxa0QoS:xa0structurexa0andxa0costxa0model.”ACMxa0SIGCOMMxa0Computerxa0Communicationxa0Review2005;xa035(2):13–22.xa0和xa0[2]xa0Jiangxa0S.,“Differentiatedxa0Queueingxa0Servicexa0(DQS)xa0forxa0End-to-Endxa0QoSxa0Provisioning:xa0Anxa0evaluationxa0fromxa0Per-Flow,xa0Per-Classxa0toxa0Per-Packet.”xa0xa0Recentxa0Advancesxa0inxa0Providingxa0QoSxa0andxa0Reliabilityxa0inxa0thexa0Futurexa0Internetxa0Backbone,xa0Novaxa0Science:xa0Newxa0York,xa02011)。该方案的主要思想是:每个数据包携带其时延要求,路由器根据数据包的时延要求决定其在缓存队列里的位置,从而保障数据包的服务质量。差分队列服务方案的主要优点是,由于服务质量要求是由数据包携带,因而具有可扩展性;另外,由于该方案将新到的数据包按时延要求放入队列的合适位置,因而具有数据包粒度的服务质量保障;最后,该方案的队列由差分队列服务队列和一个或几个其他队列组成,因而调度非常简单。xa0xa0xa0xa0实现差分队列服务的一个关键技术问题是如何快速地将新到的数据包按服务质量要求放入队列合适的位置。这是因为,数据包入队这种操作所消耗的时间会影响端到端服务质量的保障和网络资源的利用率。具体表现在,如果新数据包没有在有效时间内被放到合适的位置,就有可能得不到及时的服务,从而影响服务质量。另外,如果上述操作消耗过多的时间,将会影响系统的性能,从而降低网络资源利用率,尤其是在高速网络中这种问题更加突出。在现有技术中,综合服务和区分服务一般采用多个优先级队列提供服务质量,差分队列服务主要采用差分队列服务队列提供服务质量,这些队列的特点是采用单一的数据包入队规则。综合服务和区分服务的多优先级队列机制要求每个数据包到达时都要在所有队列中查找该数据包所属的队列。采用单一数据包入队规则的差分队列服务队列要求每次数据包到达时均要发起查找插入过程。以上数据包入队规则一般要求在一个数据包服务时间内完成新数据包的查找插入过程,因而对处理器和存储器访问操作提出了严格的要求,然而硬件实现上的难度限制了以上服务方案的数据包入队的速率和效率,使其成为高速网络的瓶颈。
发明内容
本发明的目的是解决如何快速地将新到的数据包按服务质量要求放入队列合适的位置这个关键问题,因此提供一种用于差分队列服务系统的数据包快速入队方法,减少数据包入队操作所消耗的时间,加快数据包入队速度,使其适用于高速网络。为了达到上述目的,本发明公开的差分队列服务系统的队列由差分队列服务队列和其他队列构成,差分队列服务队列包括先进先出区间和差分队列服务区间;所述先进先出区间位于队列前部,差分队列服务区间紧随其后;设先进先出区间长度为L,差分队列服务区间阈值为H,根据队列长度以及各区间的入队规则将新数据包快速插入队列。本发明通过如下技术方案实现:一种用于差分队列服务系统的数据包快速入队方法,包括如下步骤:1)新数据包到达系统,从该数据包的包头读取端到端时延;2)判断端到端时延是否大于0:是,则跳往步骤3);否,则放入其他队列,本数据包入队过程结束;3)判断当前差分队列服务队列的长度是否小于L:是,则执行步骤4);否,则跳往步骤5);4)判断当前差分队列服务队列的服务时间与该数据包的服务时间之和是否不大于该数据包所容忍的最大时延:是,则放入先进先出区间的尾部,本数据包入队过程结束;否,则放入其他队列,本数据包入队过程结束;5)xa0确定新数据包在差分队列服务区间的插入位置;6)判断新数据包在差分队列服务区间的插入位置是否同时满足如下条件,a)该数据包插入位置前面所有数据包的服务时间与该数据包的服务时间之和不大于该数据包所容忍的最大时延,b)该数据包插入位置后面的数据包的时延保障不受影响:是,则将数据包插入步骤5)所确定的位置,本数据包入队过程结束;否,则将该数据包放入其他队列,本数据包入队过程结束。本发明提供的数据包快速入队方法,所述差分队列服务系统有一个差分队列服务队列,该队列是实现服务质量保障的主要队列。所述差分队列服务队列调度优先级高于其他队列。其他队列为一个或一个以上。所述步骤5)确定新数据包在差分队列服务区间的插入位置包括:判断当前差分队列服务队列的长度是否小于L与H之和:是,则用顺序查找法确定;否,则用二分查找法确定。插入位置满足:新数据包与当前差分队列服务区间的数据包按数据包的最迟离开时刻升序排列。所述顺序查找法从当前差分队列服务区间尾部开始查找。所述二分查找法从当前差分队列服务区间的实际长度的中间位置开始查找。所述方法查找的范围均为当前差分队列服务区间的实际长度。所述先进先出区间长度L由如下条件确定:服务完先进先出区间的数据包所需时间,不得大于时间t1与时间t2之和;所述时间t1为先进先出区间查找特定位置时间,该位置使新数据包与该区间的数据包按数据包的可容忍的最迟离开队列时刻升序排列;所述时间t2为将新数据包插入查找到的位置的时间。所述差分队列服务区间阈值H由如下条件确定:用顺序查找法的平均查找时间不得大于用二分查找法的平均查找时间。相对于现有技术,本发明具有如下优点和有益效果:1、本发明公开的用于差分队列服务系统的数据包快速入队方法将该系统的差分队列服务队列划分为差分队列服务区间和先进先出区间,先进先出是内存访问操作最少、最易实现的服务规则,差分队列服务是基于数据包粒度的服务质量方案,本发明方法兼有两者的优点,既提高了数据包入队的速率和效率,又能提供服务质量保障。2、根据阈值H的确定方法,确保在差分队列服务区间确定新数据包的位置的查找算法平均查找时间最短,进一步提高数据包入队的速率和效率。
附图说明
图1为本发明差分队列服务队列区间划分示意图。图2为本发明差分队列服务系统的队列结构示意图。图3为本发明数据包快速入队的流程图。
具体实施方式
下面结合附图1~3和实施例对本发明作进一步的说明,但是本发明要求保护的范围并不局限于实施方式表述的范围。xa0如图1所示,差分队列服务队列包括先进先出区间和差分队列服务区间;所述先进先出区间位于队列前部,差分队列服务区间紧随其后;设先进先出区间长度为L,差分队列服务区间阈值为H。先进先出区间长度L必须满足服务完先进先出区间的数据包所需时间,不得大于时间t1与时间t2之和;所述时间t1为先进先出区间查找特定位置时间,该位置使新数据包与该区间的数据包按数据包的可容忍的最迟离开队列时刻升序排列;所述时间t2为将新数据包插入查找到的位置的时间。差分队列服务区间阈值H必须满足用顺序查找法的平均查找时间不得大于用二分查找法的平均查找时间。如图2所示,差分队列服务系统包括差分队列服务队列和一个或几个其他队列,差分队列服务队列与其他队列遵从严格优先级调度规则:当差分队列服务队列非空时,调度器从差分队列服务队列选择数据包进行调度;只有当差分队列服务队列为空时,才从其他队列选择数据包进行调度。实施例如图3所示,一个新的数据包到达差分队列服务系统,触发数据包快速入队,包括如下步骤:(301):当接收到一个新的数据包时,触发数据包入队过程,执行步骤302。(302):从数据包的包头中读取该数据包的端到端时延,判断该时延是否大于0。是,则执行步骤303;否,则跳往步骤311。(303):当前时刻差分队列服务队列长度是否小于先进先出区间长度L。是,执行步骤304;否,则跳往步骤306。(304):判断是否能满足新数据包的时延要求。设新数据包可容忍的最迟离开时刻为e_f,该数据包的包长为L_f,当前时刻为t,差分队列服务队列的长度为q(t),数据包转发速率为C。如果满足xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="322"/>,则,能满足新数据包的时延要求,执行步骤305;否,则跳往步骤311。(305):数据包直接进入先进先出区间的尾部,差分队列服务队列长度增加L_f。然后跳往步骤312。(306):判断当前时刻差分队列服务队列的长度是否小于(H+L)。是,执行步骤307;否,则跳往步骤308。(307):调用顺序查找法,确定数据包在差分队列服务区间的插入位置,使其按数据包的最迟离开时刻升序排列,查找结束后,返回查找到的位置g,然后跳往步骤309。(308):调用二分查找法,确定数据包在差分队列服务区间的插入位置,使其按数据包的最迟离开时刻升序排列,查找结束后,返回查找到的位置g,然后跳往步骤309。(309):判断查找到的位置g是否满足如下条件:(1)该数据包插入位置前面所有数据包的服务时间与该数据包的服务时间之和不大于该数据包所容忍的最大时延,即:ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="357"/>,(2)该数据包插入位置后面的数据包的时延保障不受影响,即: ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="440"/>。这里,e_f表示新数据包可容忍的最迟离开时刻,L_f表示新数据包的包长,L_i表示差分队列服务区间第i个数据包的包长,N表示差分队列服务区间现有的数据包数量,t表示当前时刻,L表示差分队列服务队列的先进先出区间长度,C表示数据包转发速率,xa0e_j表示差分队列服务区间第j个数据包可容忍的最迟离开时刻。xa0如果同时满足(1)和(2),则执行步骤310;否,则跳往步骤311。(310):数据包插入g后面,差分队列服务队列长度增加L_f,然后跳往步骤312。(311):数据包进入差分队列服务队列外的其他队列,然后跳往步骤312。(312):本数据包入队流程结束。